DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2022.56

On the Binary and Boolean Rank of Regular Matrices

Authors: Ishay Haviv and Michal Parnas

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract

A 0,1 matrix is said to be regular if all of its rows and columns have the same number of ones. We prove that for infinitely many integers k, there exists a square regular 0,1 matrix with binary rank k, such that the Boolean rank of its complement is k^Ω̃(log k). Equivalently, the ones in the matrix can be partitioned into k combinatorial rectangles, whereas the number of rectangles needed for any cover of its zeros is k^Ω̃(log k). This settles, in a strong form, a question of Pullman (Linear Algebra Appl., 1988) and a conjecture of Hefner, Henson, Lundgren, and Maybee (Congr. Numer., 1990). The result can be viewed as a regular analogue of a recent result of Balodis, Ben-David, Göös, Jain, and Kothari (FOCS, 2021), motivated by the clique vs. independent set problem in communication complexity and by the (disproved) Alon-Saks-Seymour conjecture in graph theory. As an application of the produced regular matrices, we obtain regular counterexamples to the Alon-Saks-Seymour conjecture and prove that for infinitely many integers k, there exists a regular graph with biclique partition number k and chromatic number k^Ω̃(log k).

Cite as

Ishay Haviv and Michal Parnas. On the Binary and Boolean Rank of Regular Matrices. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{haviv_et_al:LIPIcs.MFCS.2022.56,
  author =	{Haviv, Ishay and Parnas, Michal},
  title =	{{On the Binary and Boolean Rank of Regular Matrices}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{56:1--56:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.56},
  URN =		{urn:nbn:de:0030-drops-168545},
  doi =		{10.4230/LIPIcs.MFCS.2022.56},
  annote =	{Keywords: Binary rank, Boolean rank, Regular matrices, Non-deterministic communication complexity, Biclique partition number, Chromatic number}
}

Search Results

Documents authored by Parnas, Michal

On the Binary and Boolean Rank of Regular Matrices

Abstract

Cite as

Thanks for your feedback!

Could not send message